#include <stdio.h>

void insert(int newnum, tree_node* head){
	struct tree_node *newnode;
	newnode=(tree_node *)malloc(sizeof(tree_node));
	newnode->val=newnum;
	newnode->left=NULL;
	newnode->right=NULL;
	if(head!=NULL)
	  inserthelper(head, newnode); //return the head pointer
}

	void inserthelper(tree_node* head, tree_node* newnode){
		if(newnode->val>=head->val)
		{
			if(head->right==NULL)
			  head->right=newnode;
			else
			  inserthelper(head->right,newnode);
		}	
		else
		{
			if(head->left==NULL)
			  head->left=newnode;
			else
			  inserthelper(head->left,newnode);
		}
	}




void PrintInOrderTree(tree_node *head){
	if(head==NULL)
	  return ;
	PrintInOrderTree(head->left);
	printf("%d\n",head->val);
	PrintInOrderTree(head->right);
}

void PrintPostOrderTree(tree_node *head){
	if(head==NULL)
	  return ;
	PrintPostOrderTree(head->left);
	PrintPostOrderTree(head->right);
	printf("%d\n",head->val);
}

void PrintPreOrderTree(tree_node *head){
	if(head==NULL)
	  return ;
	printf("%d\n",head->val);
	PrintPreOrderTree(head->left);
	PrintPreOrderTree(head->right);
}

int TreeSumhelper(tree_node *head){
	if(head==NULL)
	 return 0;
	else
	 return (TreeSumhelper(head->right)+TreeSumhelper(head->left)+head->val);
}

int TreeSum(tree_node *head){
	return TreeSumhelper(head);	
}

typedef struct tree_node {
  int val;
  struct tree_node *left;
  struct tree_node *right;
} tree_node;

/* Fill in signatures of procedures called by main */
void PrintInOrderTree(tree_node *head);
void PrintPreOrderTree(tree_node *head);
void PrintPostOrderTree(tree_node *head);
int TreeSum(tree_node *head);
void insert(int newnum, tree_node* head);

main() {
	int num;
	if(num!=0){
	struct tree_node *head;
	head=(tree_node *)malloc(sizeof(tree_node));
	head->val=num;

	head->left=NULL;
	head->right=NULL;

	 insert(3, head);
	 insert(5, head);
    	 insert(2, head;
    	 insert(4, head);

	int sum=TreeSum(head);
	printf("\nThe sum is: %d\n",sum);

	printf("preOrder:");
    	PrintPreOrderTree(head);

   	printf("\npostOrder");
	PrintPostOrderTree(head);

	printf("\ninOrder:");
        PrintInOrderTree(head);

	}

}
